'''
https://leetcode.cn/problems/water-and-jug-problem/description/
'''
import math


class Solution:
    # 打表找规律
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        # if target > x + y: return False     # target 太大
        # x, y = max(x, y), min(x, y)
        # if x % y == 0:                      # 相等或，是倍数关系
        #     return target % y == 0
        # def gcd(a, b):
        #     return a if b == 0 else gcd(b, a % b)
        # gcd_num = gcd(x, y)
        # if gcd_num == 1: return True
        # return target % gcd_num == 0

        if target > x + y: return False     # target 太大
        return target % math.gcd(x, y) == 0


    def canMeasureWater2(self, X: int, Y: int, target: int) -> bool:
        dic = set()
        def f(x, y):
            if x == target or y == target or x+y == target:
                return True
            if (x, y) in dic:
                return False
            dic.add((x, y))
            res = f(X, y) or f(x, Y)
            if x != X:
                res = res or f(min(X, x+y), max(0, y-(X - x)))
            if y != Y:
                res = res or f(max(0, x-(Y-y)), min(y, Y))
            return res
        return f(0,0)

obj = Solution()
for X in range(1, 11):
    for Y in range(X, 11):
        for target in range(1, 20):
            if target > X + Y: break
            res = obj.canMeasureWater2(X, Y, target)
            if not res:
                print(f'X:{X}, Y:{Y}, target:{target}, canget: {res}')